package 栈和队列;

import java.util.Stack;

public class StackTest {
    private static final Stack lineStack = new Stack();

    static class Main {
        public static void main(String[] args) {
            //  conversion(100);
//            System.out.println(match("{}[()]"));
//            lineEdit("whli##ilr#e");
//            evaluationExpression("13*((7-2*4)-2/(2/1-1))#");
            String s = "#";
            String str = "#";
            System.out.println(s == str);
            hanoi(3, 'A', 'B', 'C');
        }
    }

    private static void hanoi(int n, char x, char y, char z) {
        if (n == 1) {
            move(x, 1, z);
        } else {
            hanoi(n - 1, x, z, y);
            move(x, n, z);
            hanoi(n - 1, y, x, z);
        }
    }

    private static void move(char x, int i, char z) {
        System.out.println("将" + i + "从" + x + "移动到" + z);
    }

    //表达式求值
    private static void evaluationExpression(String str) {
        Stack<Double> opnd = new Stack<>();//运算数栈
        Stack<String> optr = new Stack<>();//运算符栈
        String numberAll = "0123456789.";
        for (int i = 0; i < str.length(); i++) {
            String ch = str.charAt(i) + "";
            int index = i;
            StringBuilder stringBuilder = new StringBuilder();
            while (numberAll.contains(ch) && index < str.length() - 1) {
                stringBuilder.append(ch);
                ch = str.charAt(++index) + "";
            }
            if (index > i) {
                i = index - 1;
                opnd.push(Double.parseDouble(stringBuilder.toString()));
                continue;
            }
            if (index == i) {
                if (!optr.isEmpty()) {
                    switch (precede(optr.peek(), ch)) {
                        case "<":
                            optr.push(ch);
                            break;
                        case ">":
                            if (!"({[".contains(optr.peek())) {
                                calc(optr, opnd);
                                i--;
                            } else {
                                optr.push(ch);
                            }
                            break;
                        case "=":
                            optr.pop();
                            break;
                    }
                } else {
                    optr.push(ch);
                }

            }
        }


        System.out.println(opnd.peek());

    }

    public static String precede(String front, String back) {
        if ("#".equals(back)) {
            return ">";

        }
        if ("+-".contains(front)) {
            if ("+-".contains(back) || "]})".contains(back)) {
                return ">";
            } else {
                return "<";
            }
        }
        if ("/*".contains(front)) {
            if ("({[".contains(back)) {
                return "<";
            } else {
                return ">";
            }
        }
        if ("([{".contains(front)) {
            if (")]}".contains(back)) {
                return "=";
            } else {
                return ">";
            }
        }

        return "=";
    }

    public static void calc(Stack<String> optr, Stack<Double> opnd) {
        String op = optr.pop();
        Double numberback = opnd.pop();
        Double numberFront = opnd.pop();
        switch (op) {
            case "+":
                opnd.push(numberFront + numberback);
                break;
            case "-":
                opnd.push(numberFront - numberback);
                break;
            case "/":
                opnd.push(numberFront / numberback);
                break;
            case "*":
                opnd.push(numberFront * numberback);
                break;
        }
    }

    //行编辑程序
    private static void lineEdit(String str) {
        char ch;
        for (int i = 0; i < str.length(); i++) {
            ch = str.charAt(i);
            if (ch != '\n') {
                switch (ch) {
                    case '#':
                        if (!lineStack.isEmpty()) {
                            lineStack.pop();
                        }
                        break;
                    case '@':
                        lineStack.clear();
                        break;
                    default:
                        lineStack.push(ch);
                }
            }
        }
        while (!lineStack.isEmpty()) {
            System.out.println(lineStack.remove(0));
        }
    }

    //数值转换
    private static void conversion(int num) {
        Stack stack = new Stack();
        while (num != 0) {
            int coef = num % 8;
            stack.push(coef);
            num = num / 8;
        }
        while (!stack.isEmpty()) {
            System.out.print(stack.pop() + "\t");
        }
    }

    public static boolean sMatch(Character a, Character b) {
        switch (a) {
            case '{':
                return b == '}';
            case '(':
                return b == ')';
            case '[':
                return b == ']';
        }
        return false;
    }

    //括号匹配
    public static boolean match(String str) {
        String strLeft = "{[(";
        String strRiht = "}])";
        Stack<Character> stacks = new Stack<>();
        for (int i = 0; i < str.length(); i++) {
            Character a = str.charAt(i);
            if (!strLeft.contains(String.valueOf(a)) && !strRiht.contains(String.valueOf(a))) {
                return false;
            } else if (strLeft.contains(String.valueOf(a))) {
                stacks.push(a);
            } else if (strRiht.contains(String.valueOf(a))) {
                if (!stacks.isEmpty() && sMatch(stacks.peek(), a)) {
                    stacks.pop();
                    continue;
                }
                return false;

            }

        }
        return stacks.isEmpty();
    }

    public static boolean matchSecond(String str) {
        String strLeft = "{[(";
        String strRiht = "}])";
        if (str.length() % 2 == 0) {
            for (int i = 0; i < str.length(); i++) {
                Character a = str.charAt(i);
                if (!strLeft.contains(String.valueOf(a)) && !strRiht.contains(String.valueOf(a))) {
                    return false;
                } else if (strRiht.contains(String.valueOf(a))) {
                    if (i == str.length() >> 1) {
                        int index = i - 1;
                        while (index >= 0) {
                            if (sMatch(str.charAt(index), str.charAt(i))) {
                                index--;
                                i++;
                                continue;
                            }
                            return false;
                        }
                        return true;
                    }

                }

            }

        }

        return false;
    }
}
